package q40_combinationSum2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 我们再使用used数组来帮助我们实现回溯
 * 这里我们要尽可能将过程类比于在一棵树中寻找能够符合答案的叶子节点
 * 这里的used数组就是用来判断在存在重复数字的情况下对于去重的操作
 */
public class Solution_3 {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        boolean[] used = new boolean[candidates.length];
        Arrays.fill(used, false);

        Arrays.sort(candidates);
        dfs(candidates, target, 0, 0, used);
        return res;
    }

    private void dfs(int[] candidates, int target, int sum, int beginIndex, boolean[] used) {


        if (sum == target){
            res.add(new ArrayList<>(path));
        }

        for (int i = beginIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            // used[i - 1] == true，说明同⼀树⽀candidates[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层candidates[i - 1]使⽤过
            // 所以实际上我们使用任何一个条件都能够成功
            // 但一般使用在树层中进行去重效率较高
            if (i != beginIndex && candidates[i] == candidates[i - 1] && used[i - 1] == false){
                continue;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            used[i] = true;
            dfs(candidates, target, sum, i + 1, used);
            used[i] = false;
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}
